#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
//递归（超时)
//出现大量重复计算子问题
class Solution {
public:
    int uniquePaths(int m, int n)
    {
        return dfs(m, n);
    }
    int dfs(int i, int j)
    {
        if (i == 0 || j == 0) return 0;
        if (i == 1 || j == 1) return 1;

        return dfs(i - 1, j) + dfs(i, j - 1);
    }
};

//递归改记忆化搜索
class Solution {
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>>memo(m + 1, vector<int>(n + 1));
        return dfs(m, n, memo);
    }
    int dfs(int i, int j, vector<vector<int>>& memo)
    {
        if (memo[i][j] != 0)
        {
            return memo[i][j];
        }
        if (i == 0 || j == 0) return 0;
        if (i == 1 || j == 1)
        {
            memo[i][j] = 1;
            return 1;
        }

        memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
        return memo[i][j];
    }
};
//记忆化搜索改动态规划
class Solution {
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>>dp(m + 1, vector<int>(n + 1));
        dp[1][1] = 1;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (i == 1 && j == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};